;vsp 25
;skip 1
;topmar 250
;lftmar 250
;botmar 250

	       LISP - AN AMICUS CURIAE BRIEF: SHORT FORM
			    V. R. Pratt
			      1/10/77

	(This version represents 40% of the long version, which is
available from the author at NE43-811 (3-5876).)

INTRODUCTION

	The department is presently considering the available choices
of facilities for a department-wide educational computing resource.
One such facility must be a language or languages.  Of all the
facilities (editors, processors, mass storage media, consoles, etc),
the choice of language has the greatest impact on the student, if not
on the professional programmer.  This is because every encounter he
has with software, whether on a machine, in the class-room, or in an
exam, must go through the medium of language.  For example, at present
the only choice of facilities critical to the department's various
algorithms courses (6.046, 6.073, 6.851J and 6.854J) is that of
language.

	The Ad Hoc Committee on Educational Computing Resources has
narrowed the choice to APL, PASCAL (or a similar algebraic
block-structured language) and LISP, but appears to be unwilling to
narrow the choice any further, and instead proposes to make all three
available on an equal footing.  The obvious democratic advantages of
such a solution are counter-balanced by the increased maintenance
costs associated with promising full support for a variety of
languages.  Moreover, the choice of utility language for general
classroom use (e.g. for expressing algorithms) will still be at the
discretion of the individual instructor, requiring the students to be
proficient in all languages supported for this purpose by the
department.  While it is reasonable to require our students to know
all the department's languages by the time they graduate, it is
unreasonable to expect them to know them all by the end of their first
year.  Nor is it reasonable to expect them to know them all equally
well; in fact, given the demands we already place on our students'
time, it seems unfair to demand a complete mastery of more than one
language.  A working knowledge of a variety of languages is without
doubt a vital part of a computer science education, but we should not
confuse working knowledge with complete mastery when choosing a
language for a course on the basis that the student has been exposed
to it at some time during his education.

	This position paper is intended to supply the committee with
information about LISP that can come only from someone who has used
LISP extensively yet who has also had a comparable exposure to other
languages competitive with LISP.  In my own case I used the
implementation of ALGOL due to Randell and Russell [9] from 1964 to
1969 at the Basser Computing Department of the University of Sydney,
and also taught ALGOL for approximately fifty contact hours in several
departmental "crash courses".  My LISP experience extends from 1970 to
now.  It is hoped that the deeper understanding of LISP that this
paper attempts to supply will be of value to the committee in
determining the optimal number of languages to be given full support
by the department.

	There being no universally agreed on dialect of LISP to date,
I have chosen to describe MACLISP, the dialect implemented at MIT. 
(The major alternative dialects are INTERLISP, formerly BBN-LISP, and
UCI-LISP, a derivative of Stanford's LISP 1.6.)  Even with such a
concrete object as an implementation there is room for interpretation
of what has been implemented.  Thus it must be realized that the
following represents one individual's perspective on one dialect of
LISP.

	To a non-LISP-user, LISP's most forbidding aspect is its
notation, and so it is appropriate before entering the main discussion
to say a word or two about this.  To many LISP users the standard
notation offers advantages such as simplicity, ease of learning, and
the appearance of being data (as indeed it actually is).  However,
those who feel comfortable with algebraic languages and do not require
anything else need not be put off by the standard notation.  MACLISP
has an alternative extensible algebraic syntax (called "CGOL") which
is similar to that of popular algebraic languages such as ALGOL and
PL/I, except that, being just a notational variant of LISP, it
inherits the many advantages of LISP that we document below.  Item 6
of section A contains an ALGOL program together with its remarkably
similar translation into this algebraic variant of LISP.

MERITS OF LISP

	There are ten sections below, with first sentences as follows.

1.	LISP is versatile.
2.	LISP is efficient.
3.	LISP uses a standard character set.
4.	LISP is interactive.
5.	LISP is modular.
6.	LISP is notation-independent.
7.	LISP is applicative.
8.	LISP is widely used in academia.
9.	LISP is used by half the MIT Computer Science faculty.
10.	No other language enjoys all the above advantages of LISP.

1.	LISP is versatile.  Although LISP is caricatured by non-LISP
users as being of use mainly for manipulation of irregularly
structured data, this caricature does little justice to the careful
work done by McCarthy, Levin and others in the formative years of LISP
(around 1960) in developing a mathematically clean yet general
programming language.  Certainly Artificial Intelligence applications
were a concern during that development; after all, AI was the nutrient
medium within which LISP developed.  Yet the language has managed to
remain remarkably free of the concessions one might expect to arise
from such pressures, and is in our view one of the most
domain-independent languages currently enjoying wide usage.

	We may illustrate LISP's versatility by reference to its data
types.  These are:

	numbers		integers (unlimited size), reals
	bit vectors	various applications, e.g. PASCAL's sets
	booleans	T and NIL (for false)
	atoms		serving double duty as strings and variables
	lists		for which LISP is best known
	property lists	various applications, e.g. PASCAL's records
	arrays		unrestricted as to type or dimension
	function(al)s	using LAMBDA and APPLY
	programs	using EVAL and QUOTE

	In the MACLISP implementation the above data types are almost
"first-class citizens," a term used by the implementors of POP-2 [5]
to describe a data type that can be passed as a parameter, returned by
a function as a value, assigned to a variable, and tested for
equality.  LISP's data types include some for which equality cannot be
decided, namely the last two.  If we rule out the last requirement,
then all LISP data types are first-class citizens.

	It is hard to appreciate what first-class citizenship really
means until one has programmed with and without it.  A generation of
LISP programmers has capitalized on this asset of LISP in order to
express themselves more economically yet more clearly.  The examples
one finds in textbooks and manuals of LISP generally confine
themselves to lists and numbers, but the same style carries over to
the other data types of LISP when they are made available as
first-class citizens.

2.	LISP is efficient.  Another myth popular among non-LISP users
is that to use LISP one resigns oneself to gross inefficiency.
To put this shibboleth to the test, members of the MACSYMA project
took some numerical benchmark programs of the sort that one would
normally think of as being well-suited to FORTRAN compilation, and
compared their running times under each of an (admittedly old) FORTRAN
compiler and the LISP compiler used at MIT on ITS [1].  Both
compilations were performed on the same machine, a PDP-10.  The LISP
compiler won!  With a little thought it becomes apparent that
inefficient object code does not inhere in a language but rather is
the result either of the program demanding something difficult such as
a complicated parameter-passing task, or of the compiler-writers not
doing a good job.  After all, why should the FORTRAN statement
      A(I,J) = B(I,K)*C(K,J)
and the LISP statement
      (STORE (A I J) (TIMES (B I K) (C K J)))
produce different object code?  In fact, in the experiment cited
above, the slight superiority of the LISP code (involving an
insignificant factor of about 1.2) was traceable not to the code
generated for the arithmetic parts of the program, which was almost
identical in each case, but rather to the more efficient procedure
calling in LISP.  This I feel convincingly disposes of the argument
that FORTRAN (and hence presumably most other high level languages) is
more appropriate when efficiency is needed.

	Abraham Bers' Plasma Dynamics group at MIT, which although in
EECS is not a part of the Computer Science laboratories (LCS and AI),
does considerable "number crunching," having used several hundred
hours of computer time for a variety of heavily numerical problems. 
John L. Kulp of that group has experimented with a few numerical
problems using FORTRAN on MULTICS and the 370/168, and LISP (under
MACSYMA) on a PDP10 with a KL-10 processor.  Although the arithmetic
unit on the 168 has twice the speed of that on the KL-10, that group
has chosen to do most of their work on the PDP-10 in LISP/MACSYMA,
both because that factor of two is considerably diluted by the
associated and inevitable non-numeric processing and because of the
advantages of LISP over FORTRAN.  (It should be noted that MACSYMA
uses an algebraic notation, removing any notational advantage FORTRAN
may possess over the standard LISP notation.)

3.	LISP uses a standard character set.  Essentially all
general-purpose terminals on the market now adhere pretty closely to
the ASCII standard character set.  It would be next to unthinkable for
a language designer today to propose a language that made heavy use of
a radically different character set, so this claim almost goes without
saying.

4.	LISP is interactive.  If one wants to know the value of 1+1
while "talking to" LISP, one types (PLUS 1 1) (or 1+1) and LISP
replies 2 without further ado.  If one wants to get a big job
underway, one simply invokes the top-level function of that job in
exactly the same way.  And of course one's program can always type
directly to the user and accept input from him at any time.  Perhaps
more significantly, one can interact with one's program while it is
running, interrupting to both modify and/or examine the environment. 
In powerful languages like LISP, environment examination is made more
complicated by the complexity of the environment; nevertheless LISP
provides the tools needed to explore nested contexts and complex data
structures.

5.	LISP is modular.  One of the joys of programming in LISP is
that almost everything one does can be done incrementally, either on
the user's command or under program control.  If one is running a LISP
program and wants to interrupt it to write another function, one can
do so on the spot without having to re-read the whole program back
into LISP.  If one takes a dislike to the behavior of the lexical
analyzer, its behavior can be modified on the spot, either locally or
by wholesale and instantaneous replacement with a new analyzer.  If
the routine used by the top-level listen loop to print the answer is
inappropriate to the task, it can be changed in one command; in fact,
the entire top-level listen loop can be replaced.  If a given
system-defined function such as PLUS is not to the user's taste he can
simply supply his own, without having to change every occurrence of
PLUS in his program to a user-defined name.  Even the READ function
invoked by the top-level listen loop can be replaced with a user
supplied function, an advantage so important that we afford it special
treatment in the next section.

	LISP's modularity is important not only to a single programmer
but to groups of programmers cooperating on a project.  When one
develops a LISP program for a specific application, it can be used
later as a subroutine of somebody else's program.  While this is true
to a limited extent of most languages, it holds to a much greater
extent in LISP.

6.	LISP is notation-independent.  Mathematically speaking, LISP
programs form a set containing "atoms" and closed under the pairing
function CONS.  How such programs are to be represented is an
implementation-dependent issue.  In any implementation there are at
least two representations, internal (consisting in the interpreted
case of a graph whose nodes are computer words and whose edges are
pointers, and in the compiled case of a string of machine
instructions) and external (consisting traditionally of fully
parenthesized prefix (forward Polish notation) expressions).  However,
this does not exhaust the possible representations of LISP programs by
any means, a point that is frequently over-looked and yet one that was
made right at the outset by McCarthy, who used what he called MLISP
notation, an algebraic notation that PL/I users would feel much more
comfortable with than the fully parenthesized prefix notation.  An
implementation of MLISP exists at Stanford, and is the notation of
choice for LISP users there.  At MIT an MLISP-like notation called
CGOL is available to the LISP user: at any time, even half-way through
running his program, he can simply say (CGOL) and from then on he can
rephrase
 (QUOTIENT (PLUS (MINUS B) (SQRT (DIFFERENCE (EXPT B 2)
					     (TIMES 4 A C))))
	   (TIMES 2 A))
as  
(-b+sqrt(b**2-4*a*c))/(2*a)
or
(MAPCAR '(LAMBDA (I J) (PRINT (CAT '|Buy | I '| for | J '| dollars.|)))
	SHOPPINGLIST
	PRICELIST)
as
for i in shoppinglist, j in pricelist do
  print "Buy " ↑ i ↑ " for " ↑ j ↑ " dollars."

and so on.  The versatility of LISP in comparison to most other
programming languages becomes more apparent in an algebraic notation
because a more direct comparison is possible without the distraction
of having to allow for radically different styles of notation.

	MACSYMA users also use an MLISP-like algebraic notation - in
fact MACSYMA's parser is just the CGOL parser modified (by Michael
Genesereth) to handle typed expressions.  Unlike CGOL in plain LISP,
MACSYMA notation is the default language for MACSYMA users.

	It may be instructive to compare an ALGOL program taken
verbatim from the Communications of the Association for Computing
Machinery, Algorithm 482 [3], with its rendering in this algebraic
dialect of LISP.  We give the ALGOL version first, changing only its
comment section for the sake of brevity.  An explanation of what the
algorithm is doing appears in the long form.

pλ←rλ←oλ←cλ←eλ←dλ←uλ←rλ←eλ← orbits(ind, orb, im, n, k);
  vλ←aλ←lλ←uλ←eλ← n, k; iλ←nλ←tλ←eλ←gλ←eλ←rλ← n, k;
  iλ←nλ←tλ←eλ←gλ←eλ←rλ← aλ←rλ←rλ←aλ←yλ← ind, orb, im;
bλ←eλ←gλ←iλ←nλ←
  iλ←nλ←tλ←eλ←gλ←eλ←rλ← q, r, s, j, nt, ns, norb;
  fλ←oλ←rλ← j := 1 sλ←tλ←eλ←pλ← 1 uλ←nλ←tλ←iλ←lλ← n dλ←oλ← ind[j] := 0;
  norb := 0; ns := 1;
  fλ←oλ←rλ← r := 1 sλ←tλ←eλ←pλ← 1 uλ←nλ←tλ←iλ←lλ← n dλ←oλ← iλ←fλ← ind[r] = 0 tλ←hλ←eλ←nλ←
  bλ←eλ←gλ←iλ←nλ←
    norb := norb + 1; ind[r] := norb;
    nt := ns; orb[ns] := -r; s := r;
a:
    ns := ns + 1;
    fλ←oλ←rλ← j := 1 sλ←tλ←eλ←pλ← 1 uλ←nλ←tλ←iλ←lλ← k dλ←oλ←
    bλ←eλ←gλ←iλ←nλ←
      q := im[s,j];
      iλ←fλ← ind[q] = 0 tλ←hλ←eλ←nλ←
      bλ←eλ←gλ←iλ←nλ←
	nt := nt + 1; orb[nt] := q; ind[q] := norb
      eλ←nλ←dλ←
    eλ←nλ←dλ←;
    iλ←fλ← ns ≤ nt tλ←hλ←eλ←nλ←
    bλ←eλ←gλ←iλ←nλ← s := orb[ns]; gλ←oλ← tλ←oλ← a eλ←nλ←dλ←
  eλ←nλ←dλ←
eλ←nλ←dλ←

	The following is the LISP rendering of the above procedure,
using the algebraic dialect.  For direct comparison we have adhered as
closely as possible to the layout of the above program.

define "ORBITS"(ind, orb, im, n, k);
(
  new q, r, s, j, nt, ns, norb;
  for j in 1 to n do ind(j) := 0;
  norb := 0; ns := 1;
  for r in 1 to n do if ind(r) = 0 then
  (prog;		% necessitated by the presence of (ugh) goto %
    norb := norb + 1; ind(r) := norb;
    nt := ns; orb(ns) := -r; s := r;
a;
    ns := ns + 1;
    for j in 1 to k do
    (
      q := im(s,j);
      if ind(q) = 0 then
      (
	nt := nt + 1; orb(nt) := q; ind(q) := norb
      )
    );
    if ns <= nt then
    ( s := orb(ns); go a )
  )
)

	The few differences are for the most part self-explanatory.
The use of () for begin-end follows the ALGOL 68 lead.  LISP only
offers gλ←oλ←tλ←oλ← inside a PROG, whence the use of "prog".  We give below
another version of the same algorithm, this time relaxing the
constraint that we have to mimic the ALGOL solution as closely as
possible.  A detailed explanation of the algorithm appears in the long
version of this paper; here the reader is asked only to note that when
not restricted to the data types of ALGOL one can substantially
shorten a program, and at the same time improve on its structure.

define "ORBITS" im;
let adi = arraydims im;
let ind = array{nil . adi⎇, n = cadr(adi) - 1, nt = nil;
for r in 1 to n do if null ind(r) then
  (ind(r) := nt := [r];
   for s in ind(r) do
      for q in im(s) do if null ind(q) then
        (ind(q) := ind(r); cdr nt := [q]; nt := cdr nt));
ind

7.	LISP is applicative.  That is, one can write non-trivial
programs in LISP using only functional application.  More
significantly, this style can be used in LISP for programs that in
most other languages would have to be written iteratively or
recursively.  The two LISP functions (strictly, functionals or
combinators) that supply this power are MAPCAR and APPLY.  MAPCAR
permits a function to be applied to the elements of a list one at a
time (coordinate-wise operation) while APPLY permits an operation such
as PLUS to be applied to all the elements of the list (APL's notion of
reduction, written +/a).  APL, like LISP, offers non-applicative
features such as assignment and goto, but its users are strongly
encouraged to rely on the applicative part of APL, and (presumably) to
ensure that this happens APL offers a bare minimum of non-applicative
control structures.  A significant benefit of this style is that
reasoning about such programs can be done in the same algebraic
formalism that we have all been raised on since birth, instead of
having to invent systems of logic especially to cope with the
non-algebraic control structures of conventional programming
languages.  For example, knowing that + is associative even when
applied to equal-length vectors as opposed to scalars, we can
immediately see that (u+v)+w computes the same vector as u+(v+w),
whereas we may have to argue more indirectly about the effect of the
corresponding two programs in a non-applicative (in this case
non-vector-manipulating) language.  Vector spaces are well understood
and many of their properties carry over readily to reasoning about APL
programs.

	Let us give some examples where LISP can be used as an
applicative language.  Using (APPLY (FUNCTION PLUS) A) (or in CGOL,
plus{a⎇) for APL's +/A, where the APL vector A is represented as a
list in LISP, and using (MAPCAR (FUNCTION TIMES) A B) (or in CGOL,
times[a,b]) for APL's A*B, which multiplies vectors A and B
coordinatewise to yield a new vector of the same length as A and B, we
may get the effect of APL's +/A*B, which computes the inner product of
two vectors, via plus{times[a,b]⎇.  One way to write a one-line matrix
multiplication routine in LISP (yes, APL has no monopoly on
one-liners) would be:

	for i in x collect for j in list[{y⎇] collect plus{times[i,j]⎇ .

	(Here x and y are lists of lists of numbers representing a
list of rows of a matrix; list[{y⎇] is the transpose of y.)

8.	LISP is widely used in academia.  In a large portion of the
academic computing community LISP is either a first or a second
language.   I received last week a letter from Gene Freuder, a recent
MIT graduate now teaching at Indiana, where he is their AI
representative.  He was happy to report that in his department
"everyone speaks LISP as a mother tongue."  While one might not be
surprised to hear this about a department with a heavy AI bias, it is
a tribute to LISP's ubiquity that it should be so honored in a
department noted primarily for its work on programming languages and
multiple-valued logic.  LISP enjoys considerable use at Stanford
University, Stanford Research Institute, Xerox Palo Alto Research
Center, Carnegie-Mellon University, Bolt Beranek and Newman, IBM
Yorktown Heights (for their SCRATCHPAD system), and can even be found
as far afield as the University of Edinburgh and Japan's
Electro-Technologica Laboratories.  It is a sine qua non for any
laboratory planning to embark on AI research, as it is the lingua
franca of AI.  Three of the above institutions (Xerox PARC, IBM and
ETL) are only semi-academic, illustrating that LISP is not confined to
universities alone.

9.	LISP is used by approximately half the MIT Computer Science
faculty, which is not as far as I know a property of any other
language.  Thus choosing LISP as the main departmental language, if
one language is to be chosen ueber alles, would seem to involve the
least upheaval among the faculty.  Further, LISP as a high quality
language attracts high quality maintenance personnel.  LISP has been
maintained here not only by Jon L. White, a very experienced LISP
systems programmer, but by some of the sharpest graduate students in
the world.  Guy L. Steele, winner of the 1975 George Forsythe student
paper competition [9], the main student-paper competition in the
computer-science world, has been a shining example of such help for
several years dating back to his undergraduate days.  The situation
seems simply to be that the best languages attract the best students. 
Unless MIT suddenly experiences a dearth of good students, a fate few
of us want even to contemplate, this high quality maintenance should
continue at or near its present enviably high level.

	Not surprisingly, LISP is the classroom language for Patrick
Winston's AI course.  It is also one of the languages taught in 6.031. 
These are two of the department's core course.  In addition LISP is
used (admittedly with the CGOL dialect) in 6.046, my algorithms
course; using any other widely available language I would find many of
the algorithms I teach awkward to express.

10.	No other language enjoys all the above advantages of LISP.
This remains true even if advantages 2, 4 and 9 are omitted.

	In summary, I would say very simply that LISP would make an
excellent departmental language.  At this point it is appropriate to
include the aλ←dλ← hλ←oλ←mλ←iλ←nλ←eλ←mλ← argument that LISP, an MIT product, has had a
considerable impact on the academic computing community over the past
decade and a half, and along with magnetic core storage, CTSS, MULTICS
and MACSYMA has been responsible for making MIT close to the world's
most influential source of Computer Science ideas.

Bibliography.

(Includes some items not referenced in the short form of the paper.)

[1]	Fateman, Richard J. "Reply to an Editorial." SIGSAM Bulletin
25, 9-11.  (March 1973).

[2]	Hewitt, C. E., P. Bishop, and R. Steiger.  "A Universal
Modular ACTOR Formalism for Artificial Intelligence," Proc. IJCAI
3, p. 235. 1973.

[3]	McKay, John and E. Regener.  "Transitivity Sets."  Algorithm
482, CACM 1λ←7λ←, 8, 470.  (August 1974).

[4]	Moses, Joel. "The Function of FUNCTION in LISP." AI Memo 199,
MIT AI Lab (Cambridge, June 1970).

[5]	Popplestone, R. J.  "The Design Philosophy of POP-2."  Machine
Intelligence 3 (ed. D. Michie), 393-402, Edinburgh U. Press, 1968.

[6]	Pratt, V. R.  "Top Down Operator Precedence."  Proc. ACM
SIGACT/SIGPLAN Conf. on Principles of Programming Languages (POPL 1),
Boston.  (October 1973).

[7]	--------.  "A Linguistics Oriented Programming Language."
Proc. 3rd International Joint Conference on AI, Stanford, 1973.

[8]	--------.  "CGOL - an Alternative External Representation
For LISP Users."  MIT AI Lab Working Paper 89.  1976.

[9]	Steele, Guy Lewis Jr. "Multiprocessing Compactifying Garbage
Collection." Comm. ACM 18, 9, 495-508.  (September 1975).